1. Field of the Invention
The present invention relates to a routing method providing a requested quality of service, and more particularly to a routing method for establishing a routing based on a specific Quality of Service (QoS) requested in a transmission of multimedia information in various data communication networks.
2. Description of the Prior Art
One of general routing methods is a distance vector algorithm which is mainly used as a routing algorithm in the Internet.
An operation of such a distance vector algorithm will be described in brief hereinafter. In accordance with the distance vector algorithm, each of nodes linked to one of networks communicating together initializes the distance value associated therewith to be 0 (zero) while initializing respective distance values of the remaining nodes linked to the network to be infinite. In this state, a routing procedure is conducted for every node in order to find the shortest distance between the node and each of the remaining nodes. The shortest distances found for all nodes are registered in a routing table N. The following expression is an expression for deriving a shortest distance between two nodes:
D(v)←Min[(D(xcexd), D(xcfx89)+L(xcfx89,xcexd))
where, xe2x80x9cD(xcexd)xe2x80x9d represents the distance between an origin node, namely, a current node, and a destination node, and xe2x80x9cL(xcfx89,xcexd)xe2x80x9d represents the distance between a node xcfx89 and a node xcexd.
Information about the shortest distance derived for each node is transmitted to all nodes adjacent thereto. This procedure is repeated for each node until the node completely collects the entire shortest distance information associated with all nodes linked thereto.
Where no further information about path change is generated from any node and where there is no further information, being transmitted, in links connecting nodes, the path information collection procedure is completed because that condition corresponds to a complete collection of the entire shortest distance information.
The above mentioned distance vector algorithm provides an important advantage in that it is simple. As apparent from the above procedures, this algorithm can be easily implemented because it is very simple.
However, the distance vector algorithm has disadvantages in that it takes a relatively extended period of time and consumes a relatively increased quantity of network bandwidth because each node should collect information about all paths associated therewith. There is a more serious disadvantage in that a ping-pong phenomenon may occur. That is, information changed in each node in an environment involving a frequent change in network state and transmitted from each node to adjacent nodes may be returned to the node. Furthermore, intermediate nodes have no function for determining an optimum QoS.
Another routing method is a link-state algorithm. This link-state algorithm is a routing algorithm also called a xe2x80x9cShortest Path Firstxe2x80x9d algorithm. The link-state algorithm is provided with a distributed data based model while using a xe2x80x9cDijkstra""s Shortest Pathxe2x80x9d algorithm in order to determine a shortest path.
An operation of such a link-state algorithm will be described in brief hereinafter. In accordance with the link-state algorithm, each local node supplies the current link state thereof to other nodes. The status information of each node includes information about an interface, being in operation, of the node, transmission time taken to transmit information via the interface, and destinations to which the interface is connected.
The state information of each node is transmitted to other nodes using a flooding function. Each node receives such information from other nodes and stores the received information in its link-state database.
Using the stored information, each node determines the shortest distance path between the node and each of other nodes in accordance with the xe2x80x9cDijkstra""s Shortest Pathxe2x80x9d algorithm and stores it in its routing table.
However, the link-state algorithm has a disadvantage in that it is complex, as compared to the distance vector algorithm. There is another disadvantage in that a large quantity of bandwidth is consumed because link state information should be periodically supplied.
In accordance with the above mentioned link-state algorithm, an optimum path is initially established, based on all routing information completely collected. For this reason, when different nodes request different multimedia services, respectively, it is impossible to provide a variety of QoS meeting about the requested multimedia services because all link states and all distance vectors have been fixedly set in association with the optimum paths initially established for those nodes, so that they may be unsuitable.
For another routing method, there is a Dynamic Source Routing (DSR) algorithm. This DSR algorithm is an algorithm proposed by the xe2x80x9cMANETxe2x80x9d group of Internet Engineering Task Force (IETF). The DSR algorithm is not a general routing algorithm used in cable and radio environments, but a routing algorithm for xe2x80x9cad-hocxe2x80x9d networks, that is, specific radio mobile networks in which no base station exists. In this algorithm, any provision of QoS is not taken into consideration in association with multimedia services.
Such a DSR algorithm will be described in brief hereinafter. In accordance with the DSR algorithm, a source node, which requests transmission of data, forwards a request for setting of routing to all nodes adjacent thereto toward a destination node.
Each intermediate node, which receives routing setting requests respectively transmitted from other intermediate nodes, but being the same as that originally transmitted from the source node, forwards only the routing setting request, first-arrived thereto, toward the destination node while rejecting the remaining routing setting requests arriving later so as to avoid their transmission toward the destination node.
The routing setting request arriving to the destination node is returned to the source node along with a list of intermediate nodes through which the routing setting request was passed during the transmission thereof to the destination node. Thus, the shortest path between the source and destination nodes is established. In this state, all data packets to be transmitted contains information about the list of the intermediate nodes through which the packets are to pass. Accordingly, the data packets are transmitted in accordance with an order determined by the intermediate node list.
However, the above mentioned DSR algorithm has a disadvantage in that it can operate only in a specific network environment, that is, the xe2x80x9cad-hocxe2x80x9d radio network. Since the DSR algorithm is configured to always transmit packets along a path involving the shortest time delay, there is also a disadvantage in that no consideration for multimedia services is made.
In order to implement a routing algorithm capable of providing multimedia services in cable and radio networks, the following factors should be taken into consideration.
First, the most important problem involved in design of a routing algorithm for multimedia services is that an optimum path meeting all parameters cannot exist in accordance with conventional techniques even though at least one optimum path meeting each of those parameters may exist. Where two parameters, for example, bandwidth and time delay, are taken into consideration for a routing, the optimum path for bandwidth and the optimum path for time delay are different from each other in most cases. Therefore, it is necessary to provide a decisive protocol for determining whether or not a path established is optimum for a desired QoS, in association with a routing providing QoS.
Second, there is another problem in that mobile terminals operating in radio networks are frequently movable. Such mobile terminals frequently change the topology of the network while moving. For this reason, static routing methods are unsuitable in which a communication path is established prior to a request for a routing. Therefore, adaptive routing protocols should be taken into consideration.
Third, terminals operating in radio networks have a reduced memory space and a reduced computation ability, as compared to routers operating in cable networks. For this reason, routing protocols requiring a complex computation are unsuitable. Therefore, simple routing protocols are necessary.
Fourth, terminals operating in radio networks should run a distributed routing protocol operable in distributed environments. In the case of a protocol, in which a path is established for a routing by a central node in a radio network environment, frequent changes of data occur due to the frequent-movement characteristics of the radio terminals. It is also necessary to use terminal routing information at intervals of time for a maintenance of changed data. This results in an increased consumption of network bandwidth. For this reason, the above mentioned protocol is unsuitable in radio network environments. Consequently, for radio mobile communications, it is necessary to provide a distributed routing protocol in which routers operate to maintain and manage a minimum quantity of information required for a routing.
Therefore, the present invention has been made in view of the above mentioned problems involved in the prior art, and an object of the invention is to provide a QoS-based optimum routing method capable of providing QOS for multimedia services in general cable and radio networks.
Another object of the invention is to provide a routing method for providing route information about nodes passed between a source node and a destination node to those nodes in order to prevent re-transmission of the route information to nodes already passed, thereby preventing a waste of CPU capacity and bandwidth.
Another object of the invention is to provide a routing method capable of achieving a reduction in routing time.
Another object of the invention is to provide a routing method capable of using various route information arrived at a destination node to establish a back-up path or a multi-path for an increase in transmission rate.
Another object of the invention is to provide a routing method for providing efficient data services in an ATM-based multi-level hierarchical network.
In accordance with one aspect, the present invention provides a routing method in a data communication network for selecting the shortest path among a plurality of paths established between a single source node and a single destination node comprising the steps of: (A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links; and (B) designating a routing start point after completion of the initialization, and executing a routing process from the designated routing start point.
In accordance with another aspect, the present invention provides a routing method in a data communication network for selecting the shortest path among a plurality of paths established between a single source node and a single destination node comprising the steps of: (A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links; (B) designating a routing start point after completion of the initialization, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and (C) controlling the routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made.
In accordance with another aspect, the present invention provides a routing method in a data communication network for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of: (A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links; (B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and (C) controlling the routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made.
In accordance with another aspect, the present invention provides a routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting the shortest path among a plurality of paths established between a single source node and a single destination node comprising the steps of: (A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links; (B) designating a routing start point after completion of the initialization, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and (C) controlling the routing means to execute the routing process in response to the call in such a fashion that those of the layers once routed are not routed again, and to transmit the routing message to the routing start point from which the call is made.
In accordance with another aspect, the present invention provides a routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of: (A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links; (B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and (C) controlling the routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made.
In accordance with another aspect, the present invention provides a routing method in a data communication network for selecting the shortest path among a plurality of paths established between a single source node and each of destination nodes for multicasting comprising the steps of: (A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links; (B) designating a routing start point after completion of the initialization, calling a multi-casting routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the multi-casting routing means responding to the call; and (C) controlling the multi-casting routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made.
In accordance with another aspect, the present invention provides a routing method in a data communication network for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of: (A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links; (B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and (C) controlling the routing means to execute the routing process in response to the call in such a fashion that only one of routed paths having at least one overlapping node thereamong is selected while rejecting the remaining routed paths, and to transmit the resultant routing message to the routing start point from which the call is made.
In accordance with another aspect, the present invention provides a routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting the shortest path among a plurality of paths established between a single source node and each of destination nodes comprising the steps of: (A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links; (B) designating a routing start point after completion of the initialization, calling a multi-casting routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the multi-casting routing means responding to the call; and (C) controlling the multio-casting routing means to execute the routing process in response to the call in such a fashion that those of the layers once routed are not routed again, and to transmit the routing message to the routing start point from which the call is made.
In accordance with another aspect, the present invention provides a routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of: (A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links; (B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and (C) controlling the routing means to execute the routing process in response to the call in such a fashion that only one of routed paths having at least one overlapping node thereamong is selected while rejecting the remaining routed paths, and to transmit the resultant routing message to the routing start point from which the call is made.